import UIKit

/*:
 ## 排序算法
 排序算法分为内部排序和外部排序。
 
 内部排序：数据记录在内存中进行排序
 
 外部排序：排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要借助外存。
 
 常见的内部排序有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、技术排序等。
 
 * 冒泡排序
     * 最好情况 O(n)
     * 最坏情况 O(n^2))
     * 平均时间复杂度 O(n^2))
     * 空间复杂度 0(1)
 * 选择排序
     * 最好情况 O(n^2)
     * 最坏情况 O(n^2))
     * 平均时间复杂度 O(n^2))
     * 空间复杂度 0(1)
 * 插入排序
     * 最好情况 O(n))
     * 最坏情况 O(n^2))
     * 平均时间复杂度 O(n^2))
     * 空间复杂度 0(1)
 * 希尔排序 增量版插入排序
     * 最好情况 O(nLog^2n))
     * 最坏情况 O(nLog^2n))
     * 平均时间复杂度 O(nLogn))
     * 空间复杂度 0(1)
 * 归并排序
     * 最好情况 O(nLogn))
     * 最坏情况 O(nLogn))
     * 平均时间复杂度 O(nLogn))
     * 空间复杂度 O(n)
 * 快速排序
     * 最好情况 O(nLogn))
     * 最坏情况 O(n^2))
     * 平均时间复杂度 O(nLogn))
     * 空间复杂度 0(Logn)
 * 堆排序
     * 最好情况 O(nLogn))
     * 最坏情况 O(nLogn))
     * 平均时间复杂度 O(nLogn))
     * 空间复杂度 O(1)
 * 计数排序
     * 最好情况 O(n+k))
     * 最坏情况 O(n+k))
     * 平均时间复杂度 O(n+k))
     * 空间复杂度 O(k)
 * 桶排序
     * 最好情况 O(n+k))
     * 最坏情况 O(n^2))
     * 平均时间复杂度 O(n+k))
     * 空间复杂度 O(n+k)
 * 基数排序
     * 最好情况 O(n*k))
     * 最坏情况 O(n*k))
     * 平均时间复杂度 O(n*k))
     * 空间复杂度 O(n+k)
 */

func heapSort(_ arr: [Int]) -> [Int] {
    
    var nums = arr
    createHeap(&nums)
    print(nums)
    return []
}

func createHeap(_ arr: inout [Int]) {
    var i = arr.count
    while i > 0 {
        heapAdjast(&arr, start: i-1, end: arr.count)
        i -= 1
    }
}

func heapAdjast(_ arr: inout [Int], start: Int, end: Int) {
    let temp = arr[start]
    var father = start + 1
    var maxChild = father * 2
    
    while maxChild <= end {
        // 1. 找出左右子节点大的结点
        if maxChild < end && arr[maxChild-1] < arr[maxChild] {
            maxChild = maxChild+1
        }
        
        // 2. 比较根结点与这个最大结点
        if temp < arr[maxChild-1] {
            arr[father-1] = arr[maxChild-1]
        } else {
            break
        }
        
        father = maxChild
        maxChild = 2*father
    }
    arr[father-1] = temp
}

var numbers = [3, 6, 5, 2, 7, 9, 1, 4, 3]
print("排序前 \(numbers)")
heapSort(numbers)
